# 数字1的个数：https://leetcode-cn.com/problems/number-of-digit-one/


class Solution:
    def countDigitOne(self, n: int) -> int:
        """
        找出运算规律： 因为数字庞大，这道题的计算一定有规律公式可循，否则暴力破解只会超时

        假设数字为n：
        个位上1的个数
        1-10： 1个
        10-20： 1个
        30-40： 1个
        40-50： 1个
        每10个里有一个： 计算10的个数再乘 1个， 加上剩下：n%10， 看看大于1的多少：(个位上看规律时，还考虑不到 像计算10位上1时的： 110 ,210, 这样的分割值)
        if n%10 < 1:
            0
        elif n % 10 == 1:
            n % 10
        elif n % 10 > 1:
            1 
        
        min((n%10 - 1) + 1, 1)   最多还剩一个1， 加入得到个位数字为 7，那也只有一个1，取最小值
        总和起来就是 min(max(n % 10 -1 + 1, 0), 1)

        count = (n // 10) * 1 +  min(max(n % 10 -1 + 1, 0), 1)


        十位上的1
        1-100： 10个
        100-200： 10个
        200-300： 10个
        400-500： 10个
        每100里有一个： 计算100的个数再乘 10个 
        假如： 314，  314 % 10 还剩 14 没有统计十位上1的个数。 10， 11， 12， 13， 14 都有1，所以 个数为 4 + 1
        (14 - 10 + 1) 得到个位1，  也可能是负数， 304， 304 % 10 = 4  （4 - 10 + 1）< 0, 所以给个默认值 最小为0个。  
        也可能  324 % 10 + 1 = 25， 最多有 10个1， 所以取最小，默认10个1，，得到这个计算公式：

        if n % 100 -10 + 1 < 0:
            0
        elif 0 <= n % 100 -10 + 1 <= 10:
            n % 100 -10 + 1
        else:  
            10 
        简化写法：
        min(max(n % 100 - 10 + 1, 0), 10)

        总体上就是：
        (n // 100) * 10 +  min(max(n % 100 - 10 + 1, 0), 10)

        到这里已经发现规律了。 可以把计算每一位上的1抽象出来：
        当前位数代表 div, 个位为1， 十位为10，百位为 100
        
        (n // div*10) * divider +  min(max(n % (div*10) - div + 1, 0), div)   要注意运算符的优先级！ ，有的地方需要加括号
    
        """
        divider, count = 1, 0
        # divider 不大于这个数，就是代表从个位一直取这个数位，例如 123， 取 1， 10， 100， 1000(大于123，不进行循环了)
        while divider <= n:
            count += (n // (divider*10)) * divider +  min(max(n % (divider*10) - divider + 1, 0), divider) 
            divider *= 10
        
        return count